
package com.jstarcraft.ai.jsat.distributions.kernels;

import java.io.Serializable;
import java.util.List;

import com.jstarcraft.ai.jsat.linear.Vec;
import com.jstarcraft.ai.jsat.parameters.Parameterized;

import it.unimi.dsi.fastutil.doubles.DoubleList;

/**
 * The KernelTrick is a method can can be used to alter an algorithm to do its
 * calculations in a projected feature space, without explicitly forming the
 * features. If an algorithm uses only dot products, the Kernel trick can be
 * used in place of these dot products, and computes the inner product in a
 * different feature space. <br>
 * <br>
 * All KerenlTrick objects are {@link Parameterized parameterized} so that the
 * values of the kernel can be exposed by the algorithm that makes use of these
 * parameters. To avoid conflicts in parameter names, the parameters of a
 * KernelTrick should be of the form:<br>
 * &lt; SimpleClassName &gt;_&lt; Variable Name &gt;
 * 
 * @author Edward Raff
 */
public interface KernelTrick extends Parameterized, Cloneable, Serializable {
    /**
     * Evaluate this kernel function for the two given vectors.
     * 
     * @param a the first vector
     * @param b the first vector
     * @return the evaluation
     */
    public double eval(Vec a, Vec b);

    /**
     * A descriptive name for the type of KernelFunction
     * 
     * @return a descriptive name for the type of KernelFunction
     */
    @Override
    public String toString();

    public KernelTrick clone();

    // Cache related

    /**
     * Indicates if this kernel supports building an acceleration cache using the
     * {@link #getAccelerationCache(List) } and associated cache accelerated
     * methods. By default this method will return {@code false}. If {@code true},
     * then a cache can be obtained from this matrix and used in conjunction with
     * {@link #eval(int, Vec, List, List, List) } and
     * {@link #eval(int, int, List, List) } to perform kernel products.
     * 
     * @return {@code true} if cache acceleration is supported for this kernel,
     *         {@code false} otherwise.
     */
    public boolean supportsAcceleration();

    /**
     * Creates a new list cache values from a given list of training set vectors. If
     * this kernel does not support acceleration, {@code null} will be returned.
     *
     * @param trainingSet the list of training set vectors
     * @return a list of cache values that may be used by this kernel
     */
    public DoubleList getAccelerationCache(List<? extends Vec> trainingSet);

    /**
     * Pre computes query information that would have be generated if the query was
     * a member of the original list of vectors when calling
     * {@link #getAccelerationCache(java.util.List) } . This can then be used if a
     * large number of kernel computations are going to be done against points in
     * the original set for a point that is outside the original space. <br>
     * <br>
     * If this kernel does not support acceleration, {@code null} will be returned.
     * 
     * @param q the query point to generate cache information for
     * @return the cache information for the query point
     */
    public DoubleList getQueryInfo(Vec q);

    /**
     * Appends the new cache values for the given vector to the list of cache
     * values. This method is present for online style kernel learning algorithms,
     * where the set of vectors is not known in advance. When a vector is added to
     * the set of kernel vectors, its cache values can be added using this method.
     * <br>
     * <br>
     * The results of calling this sequentially on a lit of vectors starting with an
     * empty double list is equivalent to getting the results from calling
     * {@link #getAccelerationCache(java.util.List) } <br>
     * <br>
     * If this kernel does not support acceleration, this method call will function
     * as a nop.
     * 
     * @param newVec the new vector to add to the cache values
     * @param cache  the original list of cache values to add to
     */
    public void addToCache(Vec newVec, DoubleList cache);

    /**
     * Computes the kernel product between one vector in the original list of
     * vectors with that of another vector not from the original list, but had
     * information generated by
     * {@link #getQueryInfo(com.jstarcraft.ai.jsat.linear.Vec) }. <br>
     * If the cache input is {@code null}, then
     * {@link #eval(com.jstarcraft.ai.jsat.linear.Vec, com.jstarcraft.ai.jsat.linear.Vec) }
     * will be called directly.
     * 
     * @param a     the index of the vector in the cache
     * @param b     the other vector
     * @param qi    the query information about b
     * @param vecs  the list of vectors used to build the cache
     * @param cache the cache associated with the given list of vectors
     * @return the kernel product of the two vectors
     */
    public double eval(int a, Vec b, DoubleList qi, List<? extends Vec> vecs, DoubleList cache);

    /**
     * Produces the correct kernel evaluation given the training set and the cache
     * generated by {@link #getAccelerationCache(List) }. The training vectors
     * should be in the same order.
     * 
     * @param a           the index of the first training vector
     * @param b           the index of the second training vector
     * @param trainingSet the list of training set vectors
     * @param cache       the double list of cache values generated by this kernel
     *                    for the given training set
     * @return the same kernel evaluation result as
     *         {@link #eval(com.jstarcraft.ai.jsat.linear.Vec, com.jstarcraft.ai.jsat.linear.Vec) }
     */
    public double eval(int a, int b, List<? extends Vec> trainingSet, DoubleList cache);

    /**
     * Performs an efficient summation of kernel products of the form <br>
     * <big>&#8721;</big> &alpha;<sub>i</sub> k(x<sub>i</sub>, y) <br>
     * where <i>x</i> are the final set of vectors, and <i>&alpha;</i> the
     * associated scalar multipliers
     * 
     * @param finalSet the final set of vectors
     * @param cache    the cache associated with the final set of vectors
     * @param alpha    the coefficients associated with each vector
     * @param y        the vector to perform the summed kernel products against
     * @param start    the starting index (inclusive) to sum from
     * @param end      the ending index (exclusive) to sum from
     * @return the sum of the multiplied kernel products
     */
    public double evalSum(List<? extends Vec> finalSet, DoubleList cache, double[] alpha, Vec y, int start, int end);

    /**
     * Performs an efficient summation of kernel products of the form <br>
     * <big>&#8721;</big> &alpha;<sub>i</sub> k(x<sub>i</sub>, y) <br>
     * where <i>x</i> are the final set of vectors, and <i>&alpha;</i> the
     * associated scalar multipliers
     * 
     * @param finalSet the final set of vectors
     * @param cache    the cache associated with the final set of vectors
     * @param alpha    the coefficients associated with each vector
     * @param y        the vector to perform the summed kernel products against
     * @param qi       the query information about y
     * @param start    the starting index (inclusive) to sum from
     * @param end      the ending index (exclusive) to sum from
     * @return the sum of the multiplied kernel products
     */
    public double evalSum(List<? extends Vec> finalSet, DoubleList cache, double[] alpha, Vec y, DoubleList qi, int start, int end);

    /**
     * This method indicates if a kernel is a normalized kernel or not. A normalized
     * kernel is one in which k(x,x) = 1 for the same object, and no value greater
     * than 1 can be returned.
     *
     * @return {@code true} if this is a normalized kernel. {@code false} otherwise.
     */
    public boolean normalized();
}
